package com.zfl;

import java.util.Arrays;

public class MaxCoins {

    public static void main(String[] args) {
        int[] nums= {3,1,5,8};
        new MaxCoins().maxCoins(nums);
    }

    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newNums= new int[n+2];
        newNums[0]=1;
        newNums[n+1]=1;
        System.arraycopy(nums,0,newNums,1,n);

        int[][] dp = new int[n+2][n+2];

        for (int i = 1; i < n+1; i++) {
            dp[i][i]  = newNums[i]*newNums[i-1]*newNums[i+1];
        }

        for (int len = 2; len <= n ; len++) {
            for (int i = 1; i <= n+1-len; i++) {
                int j = i-1+len;
                for (int k = i; k <=j ; k++) {
                    int current = dp[i][k-1]+dp[k+1][j]+newNums[k]*newNums[i-1]*newNums[j+1];
                    dp[i][j] = Math.max(dp[i][j],current);
                }
            }
        }

//        System.out.println(Arrays.toString(newNums));
        return dp[1][n];
    }

}
